package chan.project.utils.routeTemplate;

import chan.project.model.dto.location.Coordinates;
import chan.project.model.entity.Location;
import chan.project.utils.DistanceCalculatorUtil;
import cn.hutool.json.JSONUtil;

import java.util.Arrays;
import java.util.List;

/**
 * 动态规划求最短路径（无起点与终点）
 */
public class DynamicRouteTemplate extends RouteTemplate {

    private static final int INF = Integer.MAX_VALUE; // 定义无穷大

    /**
     * 根据图获取最短路径(旅行商问题)
     * @param graph
     * @return
     */
    public Result minRoute(int[][] graph) {
        int n = graph.length;
        int[][] dp = new int[1 << n][n];
        int[][] path = new int[1 << n][n]; // 用于记录路径

        // 初始化dp数组为无穷大
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }

        // 从城市0出发，初始状态下成本为0
        dp[1][0] = 0;

        // 遍历所有状态
        for (int mask = 1; mask < (1 << n); mask += 2) {
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) == 0) continue; // 如果城市u不在当前状态中，跳过
                for (int v = 0; v < n; v++) {
                    if ((mask & (1 << v)) != 0) continue; // 如果城市v已经访问过，跳过
                    int nextMask = mask | (1 << v); // 更新状态
                    // 对于下一步，从u到v的路径成本加上当前状态的成本
                    if (dp[mask][u] != INF) { // 确保dp[mask][u]有效
                        if (dp[nextMask][v] > dp[mask][u] + graph[u][v]) {
                            dp[nextMask][v] = dp[mask][u] + graph[u][v]; // 更新成本
                            path[nextMask][v] = u; // 记录路径
                        }
                    }
                }
            }
        }

        // 找到返回起点的最小成本
        int result = INF;
        int lastCity = -1;
        int finalMask = (1 << n) - 1; // 所有城市都已访问
        for (int u = 1; u < n; u++) {
            if (dp[finalMask][u] != INF) {
                int current = dp[finalMask][u] + graph[u][0];
                if (current < result) {
                    result = current;
                    lastCity = u; // 记录最后一个城市
                }
            }
        }

        // 如果没有找到有效路径，返回null
        if (lastCity == -1) {
            return new Result(result, null);
        }

        // 构建路径
        int[] bestPath = new int[n + 1]; // 多一个位置用于返回起点
        bestPath[n] = 0; // 设置最后回到起点
        int mask = finalMask; // 所有城市都已访问的状态
        for (int i = n - 1; i >= 0; i--) {
            bestPath[i] = lastCity; // 当前城市
            int temp = lastCity;
            lastCity = path[mask][lastCity]; // 追踪前一个城市
            mask ^= (1 << temp); // 从mask中去掉已访问的城市
        }

        return new Result(result, bestPath);
    }
}